package project2;

/*********************************************************************
 * Get an approximate alignment for k sequences of length n
 *********************************************************************/

import java.io.PrintWriter;

public class approximate {


     /*********************************************************************
     * score_matrix[][] : matrix of 4x4
     * gap_cost : the cost for a gap in the alignment
     * k : the number of the sequences to align
     * n : the size of the longest sequence
     * seq[] : the input k sequences
     *********************************************************************/

     int[][] score_matrix;
     int gap_cost, k, n;
     String[] seq;
     precomputation p;
     private double end_time = 0;
     int costs = 0;
     /*********************************************************************
     * constructor
     *********************************************************************/

     approximate(int[][] m, int g, String[] s, int i, int j, precomputation r) {
        score_matrix = m;
        gap_cost = g;
        seq = s;
        k = i;
        n = j;
        p = r;
        approximation();
    }

     public double getTime(){
         return end_time;
     }
     /*********************************************************************
     * apply the approximation method
     *********************************************************************/

     void approximation() {

        /*********************************************************************
         * I keep track of how many rows and columns I filled in the matrix
         * r: the row; c: the column
         * vals[i] = Sum on 0<=j<k, j!=i of D(seq[i],seq[j])
        *********************************************************************/

        double time = System.nanoTime();

        int i = find_center_string();
        Hirschberg_global H = new Hirschberg_global(score_matrix,gap_cost);
        char[][] M = new char[k][k*n];
        for(int j=0; j<k; j++)
            for(int l=0; l<k*n; l++)
                M[j][l] = '-';
        int r, c;
        r = 1;
        c = seq[i].length();
        for(int j=0; j<seq[i].length(); j++)
            M[0][j] = seq[i].charAt(j);
        String O = new String("");
        for(int j=0; j<k; j++) {
            if(j!=i) {
                //get the optimal alignment for seq[i] and seq[j] - O: the sequence of operations
                O = H.Hirschberg(seq[i],seq[j]);
                //extend - add the new alignment to the "global" one
                int po = 0; //the position I am in the O string
                int psj = 0; //the position I am in the seq[j] string
                //I go through each column in the already existing alignment
                int l = 0; //goes from 0 to c-1 - the columns in the alignment
                while(l<c&po<O.length()) {
                    //I test all possible cases
                    //I first check what is the operation I am at
                    if(O.charAt(po)=='M')
                        //I have a match/subsitution
                        if(M[0][l]!='-') {
                            //I don't have a gap at this position in seq[i] - I can do the match
                            M[r][l] = seq[j].charAt(psj);
                            //I increase po, psj and l
                            po++;
                            psj++;
                            l++;
                            if(l==c&po!=O.length())
                                c++;
                        }
                        else {
                            //I have a gap - I move forward
                            l++;
                            if(l==c&po!=O.length())
                                c++;
                        }
                    else
                        if(O.charAt(po)=='D')
                            //I have a deletion in seq[i]
                            if(M[0][l]=='-') {
                                //I have a gap at this position in seq[i] - I can put the character from seq[j]
                                M[r][l] = seq[j].charAt(psj);
                                //I increase po, psj and l
                                po++;
                                psj++;
                                l++;
                                if(l==c&po!=O.length())
                                c++;
                            }
                            else {
                                //I don't have a gap at this position in seq[i]
                                //then I have to insert one by inserting a gap in all r lines at position l
                                for(int q=0; q<r; q++)
                                    for(int t=c; t>l; t--)
                                        M[q][t] = M[q][t-1];
                                for(int q=0; q<r; q++)
                                    M[q][l] = '-';
                                M[r][l] = seq[j].charAt(psj);
                                //I increase po, psj, l and c
                                po++;
                                psj++;
                                l++;
                                c++;
                            }
                        else
                            if(O.charAt(po)=='I')
                                //I have an insertion in seq[i]
                                if(M[0][l]!='-') {
                                    //I don't have a gap at this position in seq[i] - I can do the insertion
                                    M[r][l] = '-';
                                    //I increase po, and l
                                    po++;
                                    l++;
                                    if(l==c&po!=O.length())
                                        c++;
                                }
                                else {
                                    //I have a gap - I move forward
                                    l++;
                                    if(l==c&po!=O.length())
                                        c++;
                                }
                }
                //I increase to number of used rows
                r++;
            }
        }

        end_time = (System.nanoTime()-time)/1000000000;

        costs = cost(M,c);

        //print(costs,M,c);

    }
     public int getCosts(){return costs;}

     /*********************************************************************
     * used to compute
     * score_matrix[value(s1.charAt(i-1))][value(s2.charAt(j-1))]
     *********************************************************************/

     int value(char c){
        if(c=='a') return 0;
        if(c=='c') return 1;
        if(c=='g') return 2;
        if(c=='t') return 3;
        return -1;
    }


     /*********************************************************************
     * returns 0<=i<k such that seq[i] verifies
     * Sum on 0<=j<k, j!=i of D(seq[i],seq[j]) is minimum
     *********************************************************************/

     int find_center_string() {

        /*********************************************************************
         * min: seq[min] verifies the min condition
         * min_val: vals
         * vals[i] = Sum on 0<=j<k, j!=i of D(seq[i],seq[j])
        *********************************************************************/

        int min;
        int[] vals = new int[k];
        for(int i=0; i<k; i++)
            vals[i] = 0;
        for(int i=0; i<k-1; i++)
            for(int j=i+1; j<k; j++) {
                int x = p.get_score(i,j);
                vals[i] += x;
                vals[j] += x;
            }
        min = 0;
        for(int i=1; i<k; i++)
            if(vals[min]>vals[i])
                min = i;
        return min;
    }


     /*********************************************************************
     * returns the cost for a given alignment M
     *********************************************************************/

     int cost(char[][] M, int col) {
        int cost = 0;
        //for each column in the alignment
        for(int l=0; l<col; l++)
            //for each 2 rows
            for(int i=0; i<k-1; i++)
                for(int j=i+1; j<k; j++) {
                    //add the cost of M[i][l] and M[j][l]
                    //if one of them is a gap I add the gap cost
                    if((M[i][l]=='-')||M[j][l]=='-') {
                        //I have to test first that they're not both gaps
                        if(!(M[i][l]=='-'&&M[j][l]=='-'))
                            cost += gap_cost;
                    }
                    //I have a match/substitution
                    else
                        cost += score_matrix[value(M[i][l])][value(M[j][l])];
                }
        return cost;
    }



     /*********************************************************************
     * prints the alignment and it's cost
     *********************************************************************/

     void print(int cost, char[][] M, int c) {
        System.out.println();
        System.out.println("--------------------------------------");
        System.out.println("Approximation");
        System.out.println("--------------------------------------");
        System.out.println("Taken time in s: "+ end_time);
        System.out.println("Score: "+cost);
        System.out.println("--------------------------------------");
        System.out.println();
        System.out.println();
        for(int i=0; i<k; i++) {
            for(int j=0; j<c; j++)
                System.out.print(M[i][j]);
            System.out.println();
        }
    }

}

